#include<vector>
#include<string>
using namespace std;
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>>dp(s.length() + 1);
        for (int i = 0; i < dp.size(); ++i)
            dp[i].resize(p.length() + 1);
        dp[0][0] = true;
        for (int i = 0; i <= s.length(); ++i) {
            for (int j = 1; j <= p.length(); ++j) {
                if (i > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.'))
                    dp[i][j] = dp[i - 1][j - 1];
                else if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (!dp[i][j] && i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))
                        dp[i][j] = dp[i - 1][j];
                }
            }

        }
        return dp[s.length()][p.length()];
    }
};

int main() {
    Solution sol;
    sol.isMatch("aab", "c*a*b");
}